package com.gxc.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 */
public class Partition {

    public static void main(String[] args) {
        String s = "aab";
        System.out.println(s.substring(0,3));

        partition(s);
        System.out.println("");
    }

    public static List<List<String>> partition(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i-j==1) {
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j+1][i-1];
                    }
                }
            }
        }

        List<List<String>> res = new ArrayList<>();
        List<String> ans = new ArrayList<>();
        handle(0, s, dp, ans, res);
        return res;
    }

    public static void handle(int cur, String s, boolean[][] dp, List<String> ans, List<List<String>> res) {
        if (cur == s.length()) {
            res.add(new ArrayList<>(ans));
            return;
        }

        boolean[] booleans = dp[cur];
        for (int j = cur; j < booleans.length; j++) {
            if (booleans[j]) {
                ans.add(s.substring(cur, j+1));
                handle(j+1, s, dp, ans, res);
                ans.remove(ans.size() - 1);
            }
        }
    }


}
